package com.wenhao.leetcode.medium;

/**
 * 题目：https://leetcode-cn.com/problems/insert-interval/
 * 插入区间
 *
 * 插入区间之后仍然保持有序且不重叠
 *
 * 这一题就是考察二分查找吧
 *
 * @author Wenhao Tong
 * @create 2021-06-29 20:27
 */
public class LeetCode57 {

    public static void main(String[] args) {
        LeetCode57 leetCode57 = new LeetCode57();
        int[][] insert = leetCode57.insert(new int[][]{{1, 3}, {6,9}}, new int[]{2, 5});
        System.out.println();
    }

    public int[][] insert(int[][] intervals, int[] newInterval) {
        int[] arrays = new int[intervals.length * 2];
        for (int i = 0;i < intervals.length;i++) {
            arrays[2 * i] = intervals[i][0];
            arrays[2 * i + 1] = intervals[i][1];
        }
        int left = binarySearch(arrays, newInterval[0]);
        int right = binarySearch(arrays, newInterval[1]);
        if (left % 2 == 0) {
            arrays[left] = arrays[left] < newInterval[0] ? arrays[left] : newInterval[0];
        } else {
            left = left - 1;
        }
        if (right % 2 == 1) {

        }
        right = right - right % 2 + 1;
        int length = left / 2 + 1 + (2 * intervals.length - 1 - right) / 2;
        int[][] result = new int[length][2];
        for (int i = 0;i < left / 2;i++) {
            result[i][0] = arrays[2 * i];
            result[i][1] = arrays[2 * i + 1];
        }
        result[left / 2][0] = arrays[left];
        result[left / 2][1] = newInterval[right];
        for (int i = 0;i < (2 * intervals.length - 1 - right) / 2;i++) {
            result[left / 2 + i + 1][0] = arrays[right + 2 * i + 1];
            result[left / 2 + i + 1][1] = arrays[right + 2 * i + 2];
        }
        return result;
    }

    public int binarySearch(int[] arrays,int target) {
        int lo = 0;
        int hi = arrays.length;
        int mid;
        while (lo < hi) {
            mid = lo + (hi - lo) / 2;
            if (target <= arrays[mid]) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}
